|
|
Models of bounded arithmetic
Narusevych, Mykyta ; Krajíček, Jan (advisor) ; Šaroch, Jan (referee)
We study mutual relations of various versions of the pigeonhole principle over bounded arithmetic theory T1 2 (R). The main two variants are the ordinary ontoPHPn+1 n (R), formalizing that R is not the graph of a bijective function from [n + 1] into [n], and its weak version, WPHP2m m (S), formalizing that S is not the graph of an injective function from [2m] into [m]. It is known that: T2 2 (R) proves WPHP2m m (R) (with m universally quantified) and, in fact, also WPHP2m m (S) for all relations S that are □p 1(R) (= polynomial-time definable from R) (J. Paris, A. J. Wilkie and A. R. Woods (1988)), neither I∃1(R) nor T1 2 (R) prove WPHP2m m (R), (J. Paris and A. J. Wilkie (1985) and J. Krajicek (1992)), full T2(R) does not prove ontoPHPn+1 n (R), (M. Ajtai (1988), J. Krajicek, P. Pudlak and A. R. Woods (1991), T. Pitassi, P. Beame and R. Impagliazzo (1993)). We generalize the method of J. Paris and A. J. Wilkie (1985) to show that theory T1 2 (R) plus ∀m WPHP2m m (□p 1(R)) does not prove ontoPHPn+1 n (R). This does follow from results mentioned above but such a combined proof involves complex probabilistic combinatorics which is difficult to modify for other principles. On the other hand our method is more elementary and thus better amenable to other principles. We demonstrate this by proving a...
|
guest ::
